This invention relates to vector quantization and, more particularly, to methods for forming a lookup table having a predetermined number of attributes representing a larger number of attributes of a defined population.
The field of vector quantization generally concerns the representation of a large number of specified attributes of a given population with a smaller number of attributes which are distributed over the population to approximate the distribution of the large number of attributes. In the following discussion, the population is pixels of a video display system and the attributes are colors to be associated with the pixels. It will be understood that the processes described herein are applicable to any population which can be described by specified attributes such that the term pixel means any specified population and the term color means any selected set of attributes.
A display system for a video system, e.g. a data processing system, displays discrete colors at individual pixels. The color represented at each pixel is typically formed from a plurality of phosphors, each generating a specific color amplitude response to an activating electron beam. A typical set of phosphors may represent the primary colors red, blue, and green, from which a complete color spectrum may be formed. High resolution digital representations of color images present twenty four bit words, eight bits each for the three colors, to encode the color to be presented. This representation provides over 16 million discrete colors.
A twenty four bit color representation, however, is beyond the capability of most display systems, particularily where a real-time video capability is desired. A conventional display system uses only an eight bit word for color representation, which enables 256 colors to be selected to represent an image. The eight bit word does not, however, directly represent a color, but an address in a look-up table (LUT). The LUT then contains twenty four bit representations at each of the 256 addresses. The display system assigns each actual color to one of the stored colors in the LUT and the stored color is actually used to generate the color displayed by each pixel during the raster generation of a color display. U.S. Pat. No. 4,751,446, issued Jun. 14, 1988, to Pineda et al., incorporated herein by reference, describes one embodiment of a LUT for providing color data to a video display.
To present a high resolution color image, an optimum set of colors must be selected to represent the image. A method that will compress a color image for LUT decompression will have the following features:
1. It must produce from a list of colors in the original image a second smaller list of colors (the representative LUT colors); the representative colors need not be present in the original image. PA1 2. It must replace each of the original colors with an index into the LUT.
In one approach to color image quantization, a fixed set of color representations are stored in the LUT. The fixed set of colors may be uniformly spaced or may be based on a statistical distribution of the input colors. A uniform quantization is computationally fast, but provides poor color representations: In a statistical distribution representation, an algorithm must be selected to map the image colors onto the LUT to adequately represent the distribution of actual image colors.
A number of algorithms have been applied for this color mapping, some of which are discussed in P. Heckbert, "Color Image Quantization for Frame Buffer Display," 16 Computer Graphics, No.3, pp. 297-302 (Jul. 1982), incorporated herein by reference. In one algorithm, the densest regions in the image color distribution are selected to form the LUT. This algorithm apparently does not perform well on images with a wide variety of colors or with a small number of colors. Other algorithms attempt to define volumes in the color space, i.e., Voronoi regions, and select colors from those volumes, either as volume averages or as centroids of the volumes. Substantial computing time is required to define and iterate the Voronoi volumes.
The difficulty of selecting an optimum set of color representations for the LUT is particularly apparent in a video display having multiple windows, where multiple screens are displayed, with one screen selected for processing. The selected screen determines the LUT representations according to prior art methods. Accordingly, the selected screen may have adequate color definition, but the remaining screens typically have poor color definition since their color definition has been determined by the selected screen.
These and other problems of the prior art are addressed by the present invention wherein a LUT color representation is found without the need for defining Voronoi regions in color space suitable for color selection.
Accordingly, one object of the present invention is to generate a high resolution color representation of an image without defining Voronoi regions in the color space distribution defined by that image.
It is another object of the present invention to provide a method for quantizing color for a LUT which operates on rapid sequential displays in real time.
Additional objects, advantages and novel features of the invention will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following or may be learned by practice of the invention. The objects and advantages of the invention may be realized and attained by means of the instrumentalities and combinations particularly pointed out in the appended claims.